package geom;

import java.awt.Rectangle;
import java.awt.Shape;
import java.awt.geom.AffineTransform;
import java.awt.geom.Line2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;

/*
 * Copyright (c) 1998-2001 The Regents of the University of California. All rights reserved. See the file COPYRIGHT for details. These classes (and
 * the contained PolygonIterator class) was part of the now-closed StarJava package, gotten from it's CVS and adapted for our use. The previous
 * copyright name is a COMPLETE coincidence
 */

/**
 * A polygon shape. This class implements <b>java.awt.Shape</b>, and consists of a series of straight-line segments. This class should be used
 * instead of GeneralPath for shapes that consist only of straight-line segments and are always closed. It is more efficient than GeneralPath, and
 * allows the coordinates of vertices to be modified. Following the convention set by the Java2D shape classes, the Polygon class is an abstract
 * class, which contains two concrete inner classes, one storing floats and one storing doubles.
 */
public abstract class Polygon2D implements Shape
{

	private class PolygonIterator implements PathIterator
	{

		/**
		 * The transformed coordinates being iterated.
		 */
		private double[] _coords;

		/**
		 * The current coordinate index.
		 */
		private int _index = 0;

		/**
		 * The flag saying we are already done
		 */
		private boolean _done = false;

		/**
		 * Create a new iterator over the given polygon and with the given
		 * transform. If the transform is null, that is taken to be the same as
		 * a unit Transform.
		 */
		public PolygonIterator( Polygon2D pl, AffineTransform at )
		{
			int count = pl.getVertexCount() * 2;
			_coords = new double[count];
			if ( pl instanceof Polygon2D.Float )
			{
				Polygon2D.Float f = (Polygon2D.Float)pl;
				if ( at == null || at.isIdentity() )
				{
					for ( int i = 0; i < count; i++ )
					{
						_coords[i] = f._coords[i];
					}
				}
				else
				{
					at.transform( f._coords, 0, _coords, 0, count / 2 );
				}
			}
			else
			{
				Polygon2D.Double d = (Polygon2D.Double)pl;
				if ( at == null || at.isIdentity() )
				{
					System.arraycopy( d._coords, 0, _coords, 0, count );
				}
				else
				{
					at.transform( d._coords, 0, _coords, 0, count / 2 );
				}
			}
		}

		/**
		 * Get the current segment
		 */
		public int currentSegment( double coords[] )
		{
			int type;

			if ( _index == _coords.length )
			{
				if ( _done )
				{
					type = PathIterator.SEG_CLOSE;
				}
				else
				{
					coords[0] = this._coords[0];
					coords[1] = this._coords[1];
					type = PathIterator.SEG_LINETO;
				}
			}
			else
			{
				coords[0] = this._coords[_index];
				coords[1] = this._coords[_index + 1];
				if ( _index == 0 )
				{
					type = PathIterator.SEG_MOVETO;
				}
				else
				{
					type = PathIterator.SEG_LINETO;
				}
			}

			return type;
		}

		/**
		 * Get the current segment
		 */
		public int currentSegment( float coords[] )
		{
			int type;

			if ( _index == _coords.length )
			{
				if ( _done )
				{
					type = PathIterator.SEG_CLOSE;
				}
				else
				{
					coords[0] = (float)this._coords[0];
					coords[1] = (float)this._coords[1];
					type = PathIterator.SEG_LINETO;
				}
			}
			else
			{
				coords[0] = (float)this._coords[_index];
				coords[1] = (float)this._coords[_index + 1];
				if ( _index == 0 )
				{
					type = PathIterator.SEG_MOVETO;
				}
				else
				{
					type = PathIterator.SEG_LINETO;
				}
			}

			return type;
		}

		/**
		 * Return the winding rule. This is WIND_NON_ZERO.
		 */
		public int getWindingRule()
		{
			return PathIterator.WIND_NON_ZERO;
		}

		/**
		 * Test if the iterator is done.
		 */
		public boolean isDone()
		{
			return _done;
		}

		/**
		 * Move the iterator along by one point.
		 */
		public void next()
		{
			if ( _index == _coords.length )
			{
				_done = true;
			}
			else
			{
				_index += 2;
			}
		}
	}

	/**
	 * The current number of coordinates
	 */
	protected int _coordCount = 0;
	
	public int getCoordCount()
	{
		return _coordCount;
	}

	public abstract double[] getCoords();

	/**
	 * The flag that says the the polygon has been closed
	 */
	protected boolean _closed = false;

	/**
	 * Close the polygon. No further segments can be added. If this method not called, then the path iterators will treat the polygon as thought it
	 * were closed, and implicitly join the most recently added vertex to the first one. However, this method should generally be called, as if the
	 * last vertex is the same as the first vertex, then it merges them.
	 */
	public void closePath()
	{
		if ( getX( getVertexCount() - 1 ) == getX( 0 ) && getY( getVertexCount() - 1 ) == getY( 0 ) )
		{
			_coordCount -= 2;
		}
		_closed = true;
	}

	/**
	 * Return true if the given point is inside the polygon. This method uses a straight-forward algorithm, where a point is taken to be inside the
	 * polygon if a horizontal line extended from the point to infinity intersects an odd number of segments.
	 */
	public boolean contains( double x, double y )
	{
		if ( !this.getBounds2D().contains( x, y ) )
			return false;

		int crossings = 0;
		if ( _coordCount == 0 )
		{
			return false;
		}

		// Iterate over all vertices
		int i = 1;
		for ( ; i < getVertexCount(); )
		{
			double x1 = getX( i - 1 );
			double x2 = getX( i );
			double y1 = getY( i - 1 );
			double y2 = getY( i );

			// Crossing if lines intersect
			if ( x < x1 || x < x2 )
			{
				if ( y == y2 )
				{
					crossings++;
				}
				else if ( y == y1 )
				{
					// do nothing, so that two adjacent segments
					// don't both get counted
				}
				else if ( Line2D.linesIntersect( x, y, Math.max( x1, x2 ), y, x1, y1, x2, y2 ) )
				{
					crossings++;
				}
			}
			i++;
		}
		// Final segment
		double x1 = getX( i - 1 );
		double y1 = getY( i - 1 );
		double x2 = getX( 0 );
		double y2 = getY( 0 );

		// Crossing if lines intersect
		if ( x < x1 || x < x2 )
		{
			if ( Line2D.linesIntersect( x, y, Math.max( x1, x2 ), y, x1, y1, x2, y2 ) && ( y != y1 ) )
			{
				crossings++;
			}
		}
		// True if odd number of crossings
		return crossings % 2 == 1;
	}

	/**
	 * Return true if the given point is inside the polygon.
	 */
	public boolean contains( Point2D p )
	{
		return contains( p.getX(), p.getY() );
	}

	/**
	 * Return true if the given rectangle is entirely inside the polygon. (Currently, this algorithm can be fooled by supplying a rectangle that has
	 * all four corners inside the polygon, but which intersects some edges.)
	 */
	public boolean contains( Rectangle2D r )
	{
		return contains( r.getX(), r.getY(), r.getWidth(), r.getHeight() );
	}

	/**
	 * Return true if the given rectangle is entirely inside the polygon. (Currently, this algorithm can be fooled by supplying a rectangle that has
	 * all four corners inside the polygon, but which intersects some edges.)
	 */
	public boolean contains( double x1, double y1, double w, double h )
	{
		double x2 = x1 + w;
		double y2 = y1 + h;
		return contains( x1, y1 ) && contains( x1, y2 ) && contains( x2, y1 ) && contains( x2, y2 );
	}

	/**
	 * Get the integer bounds of the polygon.
	 */
	public Rectangle getBounds()
	{
		return getBounds2D().getBounds();
	}

	/**
	 * Get the floating-point bounds of the polygon.
	 */
	public abstract Rectangle2D getBounds2D();

	/**
	 * Get a path iterator over the object.
	 */
	public PathIterator getPathIterator( AffineTransform at, double flatness )
	{
		return getPathIterator( at );
	}

	/**
	 * Get a path iterator over the object.
	 */
	public PathIterator getPathIterator( AffineTransform at )
	{
		return new PolygonIterator( this, at );
	}

	/**
	 * Get the number of vertices
	 */
	public int getVertexCount()
	{
		return _coordCount / 2;
	}

	/**
	 * Get the given X-coordinate
	 * 
	 * @throws IndexOutOfBoundsException The index is out of bounds.
	 */
	public abstract double getX( int index );

	/**
	 * Get the given Y-coordinate
	 * 
	 * @throws IndexOutOfBoundsException The index is out of bounds.
	 */
	public abstract double getY( int index );

	/**
	 * Test if the polygon is intersected by the given rectangle. (Currently, this algorithm can be fooled by supplying a rectangle that has no
	 * corners inside the polygon, and does not contain any vertex of the polygon, but which intersects some edges.)
	 */
	public boolean intersects( Rectangle2D r )
	{
		return intersects( r.getX(), r.getY(), r.getWidth(), r.getHeight() );
	}

	/**
	 * Test if the polygon is intersected by the given rectangle.
	 */
	public boolean intersects( double x1, double y1, double w, double h )
	{
		double x2 = x1 + w;
		double y2 = y1 + h;

		if ( _coordCount == 0 )
		{
			return false;
		}

		// If the bounds don't intersect, then return false.
		Rectangle2D rect = new Rectangle2D.Double( x1, y1, w, h );
		if ( !getBounds().intersects( rect ) )
			return false;

		// return true if the polygon contains any vertex of the rectangle.
		if ( contains( x1, y1 ) || contains( x1, y2 ) || contains( x2, y1 ) || contains( x2, y2 ) )
			return true;

		// return true if the rectangle contains any vertex of the polygon
		for ( int i = 0; i < getVertexCount(); i++ )
		{
			if ( rect.contains( getX( i ), getY( i ) ) )
				return true;
		}

		// return true if any line segment of the polygon crosses a line
		// segment of the rectangle.
		// This is rather long, I wonder if it could be optimized.
		// Iterate over all vertices
		for ( int i = 1; i < getVertexCount(); i++ )
		{
			double vx1 = getX( i - 1 );
			double vx2 = getX( i );
			double vy1 = getY( i - 1 );
			double vy2 = getY( i );

			if ( Line2D.linesIntersect( x1, y1, x1, y2, vx1, vy1, vx2, vy2 ) )
			{
				return true;
			}
			if ( Line2D.linesIntersect( x1, y2, x2, y2, vx1, vy1, vx2, vy2 ) )
			{
				return true;
			}
			if ( Line2D.linesIntersect( x2, y2, x2, y1, vx1, vy1, vx2, vy2 ) )
			{
				return true;
			}
			if ( Line2D.linesIntersect( x2, y1, x1, y1, vx1, vy1, vx2, vy2 ) )
			{
				return true;
			}
		}
		return false;
	}

	/**
	 * Add a new vertex to the end of the polygon. Throw an exception of the polygon has already been closed.
	 */
	public abstract void lineTo( double x, double y );

	/**
	 * Move the start point of the vertex to the given position. Throw an exception if the line already contains any vertices.
	 */
	public abstract void moveTo( double x, double y );

	/**
	 * Reset the polygon back to empty.
	 */
	public void reset()
	{
		_coordCount = 0;
		_closed = false;
	}

	/**
	 * Set the given X-coordinate.
	 * 
	 * @throws IndexOutOfBoundsException The index is out of bounds.
	 */
	public abstract void setX( int index, double x );

	/**
	 * Set the given Y-coordinate
	 * 
	 * @throws IndexOutOfBoundsException The index is out of bounds.
	 */
	public abstract void setY( int index, double y );

	/**
	 * Transform the polygon with the given transform.
	 */
	public abstract void transform( AffineTransform at );

	/**
	 * Translate the polygon the given distance.
	 */
	public abstract void translate( double x, double y );

	/**
	 * Return a string representation of the polygon.
	 */
	@Override
	public String toString()
	{
		String out = getClass().getName() + "[\n";
		for ( int i = 0; i < getVertexCount(); i++ )
		{
			out = out + "\t" + getX( i ) + ", " + getY( i ) + "\n";
		}
		out = out + "]";
		return out;
	}

	// /////////////////////////////////////////////////////////////////
	// // Float

	/**
	 * The concrete Polygon class that stores coordinates internally as floats.
	 */
	public static class Float extends Polygon2D
	{

		/**
		 * The coordinates
		 */
		float _coords[];

		@Override
		public double[] getCoords()
		{
			float[] f = _coords.clone();

			double[] c = new double[f.length];

			for ( int i = 0; i < f.length; i++ )
			{
				c[i] = f[i];
			}

			return c;
		}

		/**
		 * Create a new polygon with space for the given number of vertices.
		 */
		public Float( int size )
		{
			_coords = new float[2 * size];
		}

		/**
		 * Create a new polygon with space for the given number of vertices.
		 */
		public Float( float[] coords )
		{
			_coords = coords;
			_coordCount = coords.length;
		}

		public Float( float[] xPoints, float[] yPoints, int nPoints )
		{
			_coords = new float[2 * nPoints];

			for ( int i = 0; i < nPoints; i++ )
			{
				_coords[i * 2] = xPoints[i];
				_coords[i * 2 + 1] = yPoints[i];
			}

			_coordCount = _coords.length;
		}

		/**
		 * Create a new polygon with no vertices.
		 */
		public Float()
		{
			this( 2 );
		}

		/**
		 * Create a new polygon with a single start point
		 */
		public Float( float x, float y )
		{
			this( 2 );
			_coords[0] = x;
			_coords[1] = y;
			_coordCount = 2;
		}

		/**
		 * Get the floating-point bounds of the polygon.
		 */
		@Override
		public Rectangle2D getBounds2D()
		{
			if ( _coordCount <= 1 )
			{
				return new Rectangle2D.Float();
			}
			float x1 = _coords[0];
			float y1 = _coords[1];
			float x2 = x1;
			float y2 = y1;
			for ( int i = 2; i < _coordCount; )
			{
				if ( _coords[i] < x1 )
				{
					x1 = _coords[i];
				}
				else if ( _coords[i] > x2 )
				{
					x2 = _coords[i];
				}
				i++;
				if ( _coords[i] < y1 )
				{
					y1 = _coords[i];
				}
				else if ( _coords[i] > y2 )
				{
					y2 = _coords[i];
				}
				i++;
			}
			return new Rectangle2D.Float( x1, y1, x2 - x1, y2 - y1 );
		}

		/**
		 * Get the given X-coordinate
		 * 
		 * @throws IndexOutOfBoundsException The index is out of bounds.
		 */
		@Override
		public double getX( int index )
		{
			return _coords[index * 2];
		}

		/**
		 * Get the given Y-coordinate
		 * 
		 * @throws IndexOutOfBoundsException The index is out of bounds.
		 */
		@Override
		public double getY( int index )
		{
			return _coords[index * 2 + 1];
		}

		/**
		 * Add a new vertex to the end of the line.
		 */
		@Override
		public void lineTo( double x, double y )
		{
			if ( _closed )
			{
				throw new UnsupportedOperationException( "This polygon has already been closed" );
			}
			if ( _coordCount == _coords.length )
			{
				float temp[] = new float[_coordCount * 2];
				System.arraycopy( _coords, 0, temp, 0, _coordCount );
				_coords = temp;
			}
			_coords[_coordCount++] = (float)x;
			_coords[_coordCount++] = (float)y;
		}

		/**
		 * Move the start point of the vertex to the given position.
		 * 
		 * @throws UnsupportedOperationException The polygon already has vertices
		 */
		@Override
		public void moveTo( double x, double y )
		{
			if ( _coordCount > 0 )
			{
				throw new UnsupportedOperationException( "This polygon already has vertices" );
			}
			_coords[0] = (float)x;
			_coords[1] = (float)y;
			_coordCount = 2;
		}

		/**
		 * Set the given X-coordinate.
		 * 
		 * @throws IndexOutOfBoundsException The index is out of bounds.
		 */
		@Override
		public void setX( int index, double x )
		{
			_coords[index * 2] = (float)x;
		}

		/**
		 * Set the given Y-coordinate
		 * 
		 * @throws IndexOutOfBoundsException The index is out of bounds.
		 */
		@Override
		public void setY( int index, double y )
		{
			_coords[index * 2 + 1] = (float)y;
		}

		/**
		 * Transform the polygon with the given transform.
		 */
		@Override
		public void transform( AffineTransform at )
		{
			at.transform( _coords, 0, _coords, 0, _coordCount / 2 );
		}

		/**
		 * Translate the polygon the given distance.
		 */
		@Override
		public void translate( double x, double y )
		{
			float fx = (float)x;
			float fy = (float)y;
			for ( int i = 0; i < _coordCount; )
			{
				_coords[i++] += fx;
				_coords[i++] += fy;
			}
		}

	}

	// /////////////////////////////////////////////////////////////////
	// // Double

	/**
	 * The concrete Polygon class that stores coordinates internally as doubles.
	 */
	public static class Double extends Polygon2D
	{

		/**
		 * The coordinates
		 */
		double _coords[];

		@Override
		public double[] getCoords()
		{
			return _coords.clone();
		}

		/**
		 * Create a new polygon with space for the given number of vertices.
		 */
		public Double( int size )
		{
			_coords = new double[2 * size];
		}

		/**
		 * Create a new polygon with the given vertices, in the format [x0, y0, x1, y1, ... ].
		 */
		public Double( double[] coords )
		{
			_coords = coords;
			_coordCount = coords.length;
		}

		/**
		 * Create a new polygon from the specified parameters
		 */
		public Double( double[] xPoints, double[] yPoints, int nPoints )
		{
			_coords = new double[2 * nPoints];

			for ( int i = 0; i < nPoints; i++ )
			{
				_coords[i * 2] = xPoints[i];
				_coords[i * 2 + 1] = yPoints[i];
			}

			_coordCount = _coords.length;
		}

		/**
		 * Create a new polygon with no coordinates
		 */
		public Double()
		{
			this( 2 );
		}

		/**
		 * Create a new polygon with a single start point
		 */
		public Double( double x, double y )
		{
			this( 2 );
			_coords[0] = x;
			_coords[1] = y;
			_coordCount = 2;
		}

		/**
		 * Get the floating-point bounds of the polygon.
		 */
		@Override
		public Rectangle2D getBounds2D()
		{
			if ( _coordCount <= 0 )
			{
				return new Rectangle2D.Double();
			}
			double x1 = _coords[0];
			double y1 = _coords[1];
			double x2 = x1;
			double y2 = y1;
			for ( int i = 2; i < _coordCount; )
			{
				if ( _coords[i] < x1 )
				{
					x1 = _coords[i];
				}
				else if ( _coords[i] > x2 )
				{
					x2 = _coords[i];
				}
				i++;
				if ( _coords[i] < y1 )
				{
					y1 = _coords[i];
				}
				else if ( _coords[i] > y2 )
				{
					y2 = _coords[i];
				}
				i++;
			}
			return new Rectangle2D.Double( x1, y1, x2 - x1, y2 - y1 );
		}

		/**
		 * Get the number of vertices
		 */
		@Override
		public int getVertexCount()
		{
			return _coordCount / 2;
		}

		/**
		 * Get the given X-coordinate
		 * 
		 * @throws IndexOutOfBoundsException The index is out of bounds.
		 */
		@Override
		public double getX( int index )
		{
			return _coords[index * 2];
		}

		/**
		 * Get the given Y-coordinate
		 * 
		 * @throws IndexOutOfBoundsException The index is out of bounds.
		 */
		@Override
		public double getY( int index )
		{
			return _coords[index * 2 + 1];
		}

		/**
		 * Add a new vertex to the end of the line.
		 */
		@Override
		public void lineTo( double x, double y )
		{
			if ( _coordCount == _coords.length )
			{
				double temp[] = new double[_coordCount * 2];
				System.arraycopy( _coords, 0, temp, 0, _coordCount );
				_coords = temp;
			}
			_coords[_coordCount++] = x;
			_coords[_coordCount++] = y;
		}

		/**
		 * Move the start point of the vertex to the given position.
		 * 
		 * @throws UnsupportedOperationException The polygon already has vertices
		 */
		@Override
		public void moveTo( double x, double y )
		{
			if ( _coordCount > 0 )
			{
				throw new UnsupportedOperationException( "This polygon already has vertices" );
			}
			_coords[0] = x;
			_coords[1] = y;
			_coordCount = 2;
		}

		/**
		 * Set the given X-coordinate.
		 * 
		 * @throws IndexOutOfBoundsException The index is out of bounds.
		 */
		@Override
		public void setX( int index, double x )
		{
			_coords[index * 2] = x;
		}

		/**
		 * Set the given Y-coordinate
		 * 
		 * @throws IndexOutOfBoundsException The index is out of bounds.
		 */
		@Override
		public void setY( int index, double y )
		{
			_coords[index * 2 + 1] = y;
		}

		/**
		 * Transform the polygon with the given transform.
		 */
		@Override
		public void transform( AffineTransform at )
		{
			at.transform( _coords, 0, _coords, 0, _coordCount / 2 );
		}

		/**
		 * Translate the polygon the given distance.
		 */
		@Override
		public void translate( double x, double y )
		{
			for ( int i = 0; i < _coordCount; )
			{
				_coords[i++] += x;
				_coords[i++] += y;
			}
		}
	}
}
